package com.yoshino.leetcode.improve40.threetyth;

import java.util.Arrays;

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 思路：t[i] = val + t[i - 1] / t[i - 2]
        int n = cost.length;
        for (int i = 2; i < n; i++) {
            cost[i] += Math.min(cost[i - 1], cost[i - 2]);
        }
        return Math.min(cost[n - 1], cost[n - 2]);
    }

    public int rob1(int[] nums) {
        // 思路：不能相邻，i > 3: t[i] = val + t[i - 2] / t[i - 3]
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // 特殊情况
        nums[2] += nums[0];
        for (int i = 3; i < n; i++) {
            nums[i] += Math.max(nums[i - 2], nums[i - 3]);
        }
        return Math.max(nums[n - 1], nums[n - 2]);
    }

    public int rob(int[] nums) {
        // 环形：i > 4: nums[0] 或 nums[n - 1] 只能选择一个
        int n = nums.length;
        if (n < 4) {
            int res = nums[0];
            for (int i = 1; i < n; i++) {
                res = Math.max(res, nums[i]);
            }
            return res;
        }
        int[] notZero = Arrays.copyOf(nums, nums.length);
        // 要第一个
        nums[2] += nums[0];
        for (int i = 3; i < n - 1; i++) {
            nums[i] += Math.max(nums[i - 2], nums[i - 3]);
        }
        int max = Math.max(nums[n - 3], nums[n - 2]);
        // 要最后一个
        notZero[3] += notZero[1];
        for (int i = 4; i < n; i++) {
            notZero[i] += Math.max(notZero[i - 2], notZero[i - 3]);
        }
        int max2 = Math.max(notZero[n - 1], notZero[n - 2]);
        return Math.max(max2, max);
    }
}